In packet type communication modes used in the IP (Internet Protocol) network such as the Internet it is possible to reduce the communication cost more than the conventional dedicated line because a large number of users can share the line. Taking advantage of this low cost a request has risen to apply speech data, mission critical data of companies, etc. which conventionally flew on dedicated line to the IP network. Consequently, in the conventional IP network where the Best Effort type service was the mainstream there has been increasing a need to realize the communication quality such as low delay, low discard rate which the dedicated line has.
One of the services which realize the communication quality is the GFR (Guaranteed Frame Rate) which is defined as the ATC (ATM Transfer Capability) of the ATM (Asynchronous Transfer Mode) network. In the GFR it is possible to utilize the bandwidth effectively by allowing the communication exceeding the committed information rate if there is any extra bandwidth as well as guaranteeing the contracted committed information rate.
The need of the bandwidth control will be described referring to FIG. 3. Here, FIG. 3 is an example to show the configuration of a network and it is needless to say that it is applicable to both of the prior art and the present invention. In FIG. 3 output line of edge node C1 is shared by flows from both of ISP (Internet Service Provider)'s network A and ISP's network B. Consequently, it tends to be a degradation point of the communication quality when congestion occurs in communication line. Therefore, the bandwidth control is needed for transfer packet at the edge node C1.
For the bandwidth control, first, it is needed to police the contracted committed information rate for each user and guarantee it. This is to guarantee the communication quality of accommodated users A1˜A3 of the ISP's network A. At the same time, it is necessary to police and limit the peak information rate as a user group A which is a group binding the users A1˜A3 to prevent congestion and protect the bandwidth resource in carrier's backbone network. Here, each of the users A1˜A3 can send and receive packets using the extra bandwidth even when they have used up the committed information rate guaranteed for each of them, unless they exceed the peak information rate as user group A. Also, for the purpose of reduction of accommodation cost per user group, a plurality of user groups are accommodated in the edge node C1 and bandwidth policing is performed for each user group.
In Japanese Patent Application Laid-Open No.JP-A-2001-326688 (hereinafter it is called prior art 1) a shaping apparatus which guarantees the committed information rate for each user is disclosed. In the prior art 1 the continuous Leaky Bucket Algorithm (hereinafter it is called a leaky bucket algorithm) which is a bandwidth policing algorithm of cells which are fixed length packets in the ATM is used as a bandwidth policing algorithm extended to the variable length packet of the IP. The leaky bucket algorithm is a model of a leaky bucket which has a certain depth and a hole, and while the bucket contains water in it the water continues to leak in policed bandwidth and when a packet is input water in an amount of byte length of the packet is poured. The bucket has a certain depth to allow an arrival swing of packet, and the input packet is handled as a packet of which bandwidth does not exceed (keep) the contracted bandwidth while the bucket does not overflow, and when the bucket overflows the packet is handled as a packet of which bandwidth exceeds (violate) the contracted bandwidth.
FIG. 1 is a conceptual diagram of a shaping apparatus cited from the prior art 1. The shaping apparatus shown in FIG. 1 is assumed to be implemented between packet switching means which performs internal transmit processing of received packet and a packet transmit circuit which transmits processed packet.
When a packet arrives at a shaper unit 100 a discard controller 110 decides “accumulation” or “discard” of the arrived packet. A packet accumulate FIFO (First In First Out) 120 accumulates packet which is decided to be “accumulation” and transmits the packet in bandwidth which is equal to or greater than a total sum of the contracted committed information rate for each user. A bandwidth policing unit 130 checks the bandwidth for each user and handles a packet within the committed information rate as a high priority packet and handles the other as a low priority packet. By setting FIFO threshold for a high priority packet deeper than FIFO threshold for a low priority packet, it is possible to protect the high priority packet by deciding the high priority packet to be “transferred” with high priority and guarantee the committed information rate for each user. Here, FIFO is a kind of memory which accumulates packets, and it refers to a memory which has the structure in which it is possible to fetch data stored previously in order of the storage when stored data is fetched and used, or to such a storage method.
Applying the shaping apparatus of the prior art 1 to the edge node C1 of FIG. 3, the above-mentioned bandwidth control is possible. By the bandwidth policing unit 130, the bandwidth policing of the packet is performed for each received packet user and the discrimination of high priority packet/low priority packet is performed. A packet which is accommodated within the committed information rate is processed as a high priority packet. Namely, its queuing priority for the packet accumulate FIFO 120 is set to high. On the other hand, a packet which exceeds the committed information rate for each user is processed as a low priority packet. Namely, its queuing priority for the packet accumulate FIFO 120 is set to low. Thereby, the guarantee of the committed information rate for each user can be realized.
Also, the limitation of peak information rate of packet user group can be realized by setting packet transmit bandwidth from the packet accumulate FIFO 120 to an arbitrary value. Here, the packet which is to be accumulated in the packet accumulate FIFO 120 is limited to a packet of specified user group, for example, a packet of user group A. Namely, the shaper 100 is designed depending on the number of user groups.
In RFC2698 of the Internet Society, it is disclosed 2 Rate 3 Color Marker (hereinafter it is referred to as prior art 2) as a discrimination method for discriminating packets. In FIG. 2 a processing flow of the prior art 2 is shown in a flow chart. In the prior art 2, first, it is decided whether bandwidth occupied by user packet for each user exceeds the peak information rate or not, and if the bandwidth exceeds the peak information rate, the packet is decided to be a discard packet and the packet is discarded. If the bandwidth does not exceed the peak information rate, next, it is decided whether the bandwidth occupied by user packet for each user exceeds the committed information rate or not. If the bandwidth exceeds the committed information rate, the packet is decided to be a low priority packet and, as a sanction, for example, it is regarded as a packet which is to be discarded with high priority at the time of congestion by setting its queuing priority to low. If the bandwidth does not exceed the committed information rate, the packet is decided to be a high priority packet and its queuing priority is set to high so that it becomes hard to be discarded even at the time of congestion.
When trying to accommodate a plurality of user groups in the shaping apparatus disclosed in the prior art 1, to limit the peak information rate for each user group, it is needed to limit the transmit bandwidth from the packet accumulate FIFO less than or equal to the peak information rate by providing a packet accumulate FIFO for each user group. Therefore, as the number of accommodated user groups increases the number of packet accumulate FIFOs necessary to be provided increases. As the time necessary to decide the packet accumulate FIFO which transmits the packet increases along with the number of the packet accumulate FIFOs, when a large number of user groups are to be accommodated the decision processing time necessary to decide the packet accumulate FIFO increases according to the number of the user groups to be accommodated. Therefore, there is a problem that when a large number of user groups are to be accommodated the bandwidth control can not be performed at high speed. Moreover, when a large number of user groups are to be accommodated, as a large number of packet accumulate FIFOs become necessary, there is another problem that the cost to maintain the packet accumulate FIFOs increases proportionally to the number of the accommodated user groups.
If the packets which belong to different kinds of user groups are buffered using a general purpose large memory in stead of the FIFO, in principle there would be no need to provide packet accumulate FIFOs according to the user groups, but the process to decide from which user group a packet should be fetched would be needed. Consequently, the process becomes complicated and as the reading speed of the memory is not high, therefore high speed bandwidth control can not be implemented.
Also, the technique described in the prior art 2 is a technique to discriminate the received packet to be a high priority packet, a low priority packet or a discard packet using the bandwidth policing result, it can not solve the above-mentioned problems even if it is combined with the leaky bucket algorithm described in the prior art 1.